<HTML><HEAD><TITLE>bb_min(+Goal, ?Cost, ?Options)</TITLE>
</HEAD><BODY>[ <A HREF="index.html">library(branch_and_bound)</A> | <A HREF="../../index.html">Reference Manual</A> | <A HREF="../../fullindex.html">Alphabetic Index</A> ]
<H1>bb_min(+Goal, ?Cost, ?Options)</H1>
Find a minimal solution using the branch-and-bound method
<DL>
<DT><EM>Goal</EM></DT>
<DD>The (nondeterministic) search goal
</DD>
<DT><EM>Cost</EM></DT>
<DD>A (usually numeric domain) variable representing the cost
</DD>
<DT><EM>Options</EM></DT>
<DD>A bb_options structure or variable
</DD>
</DL>
<H2>Description</H2>
	A solution of the goal <EM>Goal</EM> is found that minimizes
	the value of <EM>Cost</EM>.  <EM>Cost</EM> should be a
	variable that is affected, and eventually instantiated, by
	<EM>Goal</EM>.  Usually, <EM>Goal</EM> is the search procedure
	of a constraint problem and <EM>Cost</EM> is the variable
	representing the cost.  The solution is found using the branch
	and bound method:  as soon as a solution is found, it gets
	remembered and the search is continued or restarted with an
	additional constraint on the <EM>Cost</EM> variable which
	requires the next solution to be better than the previous one. 
	Iterating this process yields an optimal solution in the end.
	<P>
	The possible options are
	<DL>
	<DT><STRONG>strategy:</STRONG></DT><DD>
	    <DL>
	    <DT>continue (default)</DT>
	    	<DD>after finding a solution, continue search with the newly
		found bound imposed on Cost</DD>
	    <DT>restart</DT>
	    	<DD>after finding a solution, restart the whole search with
		the newly found bound imposed on Cost</DD>
	    <DT>step</DT>
	    	<DD>a synonym for 'restart'</DD>
	    <DT>dichotomic</DT>
	    	<DD>after finding a solution, split the remaining cost range
		and restart search to find a solution in the lower sub-range.
		If that fails, assume the upper sub-range as the remaining
		cost range and split again.</DD>
	    </DL>
	    The new bound or the split point, respectively, are computed
	    from the current best solution, while taking into account the
	    parameters delta and factor.
	    </DD>
	<DT><STRONG>from:</STRONG></DT>
	    <DD>number - an initial lower bound for the cost (default -1.0Inf)</DD>

	<DT><STRONG>to:</STRONG></DT>
	    <DD>number - an initial upper bound for the cost (default +1.0Inf)</DD>

	<DT><STRONG>delta:</STRONG></DT>	
	    <DD>number - minimal absolute improvement required for each step
	    (default 1.0), applies to all strategies</DD>

	<DT><STRONG>factor:</STRONG></DT>
	    <DD>number - minimal improvement ratio (with respect to the lower
	    cost bound) for strategies 'continue' and 'restart' (default 1.0),
	    or split factor for strategy 'dichotomic' (default 0.5)</DD>

	<DT><STRONG>timeout:</STRONG></DT>
	    <DD>number - maximum seconds of cpu time to spend (default: no limit)</DD>

	<DT><STRONG>report_success:</STRONG></DT>
	    <DD>GoalPrefix - an atom (predicate name) or structure (goal prefix),
	    specifying a goal to be invoked whenever the branch-and-bound
	    process finds a better solution.  The invoked goal is constructed
	    by adding three arguments (Cost, Handle, Module) to GoalPrefix.
	    Cost is a float number representing the cost of the solution found,
	    Handle is a handle as accepted by bb_cost/2 or bb_solution/2,
	    and Module is the context module of the minimisation.
	    The default handler prints a message.</DD>

	<DT><STRONG>report_failure:</STRONG></STRONG></DT>
	    <DD>GoalPrefix - an atom (predicate name) or structure (goal prefix),
	    specifying a goal to be invoked whenever the branch-and-bound
	    process cannot find a solution in a cost range.  The invoked goal
	    is constructed by adding three arguments (Cost, Handle, Module) to
	    GoalPrefix.  Cost is a From..To structure representing the range
	    of cost in which no solution could be found, Handle is a handle
	    as accepted by bb_cost/2 or bb_solution/2, and Module is the
	    context module of the minimisation.
	    The default handler prints a message.</DD>
	</DL>
	The default options can be selected by passing a free variable as
	the Options-argument. To specify other options, pass a bb_options-
	structure in struct-syntax, e.g.
	<PRE>
	bb_options{strategy:dichotomic, timeout:60}
	</PRE>
	In order to maximize instead of minimizing, introduce a negated
	cost variable in your model and minimize that instead.
	<P>
	Compatibility note: For backward compatibility, the report_success and
	report_failure options also accept Name/Arity specifications with
	maximum arity 3 for the handler goals. The three optional arguments
	are then Cost, Handle, and Module.
	
<H3>Modules</H3>
This predicate is sensitive to its module context (tool predicate, see @/2).
<H2>Examples</H2>
<PRE>
?- bb_min(member(X,[9,6,8,4,7,2,4,7]), X, O).
Found a solution with cost 9
Found a solution with cost 6
Found a solution with cost 4
Found a solution with cost 2
Found no solution with cost -1.0Inf .. 1
X = 2
O = bb_options(continue, -1.0Inf, 1.0Inf, 1, 1, 0, 0, _, _)
yes.

[eclipse 6]: bb_min(member(X,[9,6,8,4,7,2,4,7]), X, bb_options{delta:4}).
Found a solution with cost 9
Found a solution with cost 4
Found no solution with cost -1.0Inf .. 0
X = 4
yes.

[eclipse 10]: bb_min(member(X,[99,60,80,40,70,30,70]), X,
	bb_options{strategy:dichotomic, from:0}).
Found a solution with cost 99
Found a solution with cost 40
Found no solution with cost 0.0 .. 20.0
Found a solution with cost 30
Found no solution with cost 20.0 .. 25.0
Found no solution with cost 25.0 .. 27.5
Found no solution with cost 27.5 .. 28.75
Found no solution with cost 28.75 .. 29.0

X = 30
yes.
</PRE>
<H2>See Also</H2>
<A HREF="../../lib/branch_and_bound/bb_min-6.html">bb_min / 6</A>
</BODY></HTML>
